Open Shortest Path First (OSPF) is a routing protocol developed for Internet Protocol (IP) networks that calls for the distribution of link-state advertisements (LSAs) among other routers. Information on attached interfaces, metrics used, and other variables may be included in OSPF LSAs. As OSPF routers accumulate link-state information, they use algorithms that calculate the shortest path to various routers (network nodes). A link-state database that provides an overall picture of networks in relationship to routers may be constructed from the collection of LSAs received from all routers in the same area. Because routers within the same area share the same information, they may have identical link-state databases.
OSPF uses hello protocol in some instances of OSPF operations. When a router using the OSPF protocol is powered up, it initializes its routing-protocol data structures and then waits for indications from lower-layer protocols that its interfaces are functional. After a router is assured that its interfaces are functioning, it uses the OSPF Hello protocol to acquire neighbors (e.g., routers with interfaces to a common link). The router sends hello packets to its neighbors and receives their hello packets. In addition to helping acquire neighbors, hello packets also act as “keepalive” messages that let routers know that other routers are still functional. On some multi-access networks (e.g., networks supporting more than two routers), the Hello protocol elects a designated router (“DR”) and a backup designated router (“BDR”). Among other things, the designated router is responsible for generating LSAs for the entire multi-access network. Designated routers allow a reduction in network traffic and in the size of the link-state database.
Link-state databases may be exchanged when two OSPF nodes (e.g., routers and/or other network devices) are trying to establish a full adjacency. To achieve full adjacency between the OSPF nodes, the link-state databases are synchronized through a database exchange procedure. A first node sends a second node a summary of a link-state database of the first node through a set of database description packets that contain a header of every link-state advertisement (LSA) in the link-state database of the first node. For every received LSA header that is contained in the database description packets, the second node compares the LSA header with a corresponding LSA instance in a link-state database of the second node. The second node sends the first node a request for the LSA if the LSA instance in the database of the second node is older or not present. Similarly, the second node sends the first node a summary of a link-state database of the second node through a set of database description packets that contain a header of every LSA in the link-state database of the second node. For every received LSA header that is contained in the database description packets, the first node compares the LSA header with a corresponding LSA instance in the link-state database of the first node. The first node sends the second node a request for the LSA if the LSA instance in the database of the first node is older or not present.
An adjacency becomes full from the point of view of the first node when the first node finishes sending the summary of the link-state database of the first node and processing all the database description packets from the second node, and gets all the LSAs from the second node that the first node has requested. An adjacency becomes full from the point of view of the second node when the second node finishes sending the summary of the link-state database of the second node and processing all the database description packets from the first node, and gets all the LSAs from the first node that the second node has requested. A full adjacency between the first node and the second node is formed successfully when an adjacency becomes full from the point of view of both the first node and the second node.
In OSPF, a reliable flooding mechanism is used to ensure that link-state databases remain synchronized. When a router generates or modifies an LSA, it must communicate this change throughout the network. The router starts the synchronization process by forwarding the LSA to each fully adjacent router. LSAs received at one router may be stored and forwarded to adjacent routers until all routers in an area have received the LSA.
Certain layer 2 networks (defined, e.g., in the Open System Interconnect (OSI) network model) may allow any-to-any communication between all nodes in the layer 2 network, with different costs associated with communication between any given pair of nodes. Costs may be expressed as simple numbers and may include such factors as distance between nodes (round-trip time), network throughput of a link, or link availability and reliability. When running the OSPF routing protocol on these layer 2 networks, the network may be modeled as a broadcast link, which requires a node on the network to have full adjacency with only one or two nodes of the network (e.g., a DR and a BDR for the layer 2 network). DRs and BDRs may also be utilized on NBMA (non-broadcast multi access) networks. However, the representation of broadcast links or NBMA links in OSPF assumes that a given node can reach all other nodes on the link with identical cost/metrics. To advertise a different cost to each of the nodes on a link, full adjacency between nodes is required. However, having each node maintain full adjacency with each of the other nodes in the layer 2 network can overburden some networks, such as low bandwidth radio networks.